package com.lw.algorithm.test;

/**
 * 斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，
 * 2584，4181，6765，10946，17711，28657，46368........
 * 这个数列从第3项开始，每一项都等于前两项之和。
 *
 */
public class Fibonacci {
	private final static int max = 1000000;

	/**
	 * 递归方法，时间复杂度2^i
	 * 
	 * @param i
	 * @return
	 */
	public static long recursion(int i) {
		if (i == 0)
			return 0;
		if (i == 1)
			return 1;
		return recursion(i - 1) + recursion(i - 2);
	}

	private static long[] temp = new long[max];

	/**
	 * 动态规划方法，将中间结果缓存起来,时间复杂度 i
	 * 
	 * @param i
	 * @return
	 */
	public static long dynamic(int i) {
		if (i == 0)
			return 0;
		if (i == 1)
			return 1;
		if (temp[i] != 0) {
			return temp[i];
		}
		temp[i] = dynamic(i - 1) + dynamic(i - 2);
		return temp[i];
	}

	public static void main(String[] args) {
//		long startTime = System.currentTimeMillis(); // 获取开始时间
//		System.out.println(recursion(40));
//		long endTime = System.currentTimeMillis(); // 获取结束时间
//		System.out.println("程序运行时间： " + (endTime - startTime) + "ms");

		long startTime2 = System.currentTimeMillis(); // 获取开始时间
		System.out.println(dynamic(100));
		long endTime2 = System.currentTimeMillis(); // 获取结束时间
		System.out.println("程序运行时间： " + (endTime2 - startTime2) + "ms");
	}
}
